#include <stdio.h>

// 二分查找函数，返回插入位置的前一个索引
int binarySearch(int arr[], int item, int low, int high) {
    if (high <= low)
        return (item > arr[low]) ? (low + 1) : low;

    int mid = (low + high) / 2;

    if (item == arr[mid])
        return mid + 1;

    if (item > arr[mid])
        return binarySearch(arr, item, mid + 1, high);

    return binarySearch(arr, item, low, mid - 1);
}

// 二分插入排序函数
void binaryInsertionSort(int arr[], int n) {
    int i, j, key, loc;

    for (i = 1; i < n; i++) {
        key = arr[i];

        // 使用二分查找找到插入位置
        loc = binarySearch(arr, key, 0, i - 1);

        // 移动元素以腾出空间
        for (j = i - 1; j >= loc; j--) {
            arr[j + 1] = arr[j];
        }
        arr[loc] = key;
    }
}

// 打印数组函数
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// 主函数
int main() {
    int arr[] = {37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前的数组: \n");
    printArray(arr, n);

    binaryInsertionSort(arr, n);

    printf("排序后的数组: \n");
    printArray(arr, n);
    return 0;
}